# 给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
#  注意：该题与 1081 https://leetcode-cn.com/problems/smallest-subsequence-of-distinct-characters 相同
#
#  示例 1：
# 输入：s = "bcabc"
# 输出："abc"
#
#  示例 2：
# 输入：s = "cbacdcbc"
# 输出："acdb"
class Solution:
    def removeDuplicateLetters2(self, s: str) -> str:
        """
        贪心 + 单调递增栈
        从结果来看，通过去重后得到的所有可能的结果字符串(不考虑顺序)长度肯定是一致的
        由LeetCode402 可以总结到:
        对于两个相同长度的字符串序列，最左边不同的字符字决定了这两个序列的字典序大小，
        因此若要使得去重后能保证相对顺序不变且字典序最小，需要保证靠前的字符尽可能小(单调栈)

        本题的三个子问题:
        1.去重：可以通过 存储每个字母出现在s中的最后的位置(也可以用dict存储每个字母出现的次数) 的方式，将每个字母出现的最后的位置记录下来。
        2.不能打乱其他字符顺序：按顺序遍历，将非重复的字母存储到答案数组或者栈中，最后再拼接起来，就能保证不打乱其他字符顺序。
        3.字典序最小：意味着字典序小的字母应该尽可能放在前面。
        :param s:
        :return:
        """
        lastOccurrence = [-1] * 26  # 记录每个字母出现在s中的最后的位置
        for i, char in enumerate(s):
            lastOccurrence[ord(char) - 97] = i

        stack = []
        charIsInStack = [False] * 26  # 记录字母是否已经出现在了单调栈中
        for i, char in enumerate(s):
            index = ord(char) - 97
            if not charIsInStack[index]:  # 字母还未出现在栈中
                # 即要将栈中比当前字母大的且不是最后一次出现的字符移除掉
                # char < stack[-1] 保证字典序最小
                # lastOccurrence[ord(stack[-1]) - 97] 保证留下的字符相对序不变
                while stack and char < stack[-1] and lastOccurrence[ord(stack[-1]) - 97] > i:
                    charIsInStack[ord(stack.pop()) - 97] = False
                stack.append(char)
                charIsInStack[index] = True
        return ''.join(stack)

    def removeDuplicateLetters1(self, s: str) -> str:
        """
        暴力贪心
        每次都选择尽可能的小字符作为本轮的首字符，
        同时要保证本轮选择的字母前的其他字母不是首次出现在当前字符串中

        递归实现
        removeDuplicateLetters1 的作用：找到当前字符串的最⼩字母，
            最小字母需要满足的条件:
                1.该字母之前的所有字母都在这个字母之后还会出现
                2.该字母的字典序要尽可能的小
        关系式:f(n)=x+f(subStr)  x:本轮找到的最⼩字母，subStr:剩余子串中剔除最小字母得到的子串
        :param s:
        :return:
        """
        if len(s) <= 1:
            return s
        lastOccurrence = [-1] * 26  # 记录每个字母出现在s中的最后的位置
        for i, curChar in enumerate(s):
            lastOccurrence[ord(curChar) - 97] = i

        pos = 0  # 用于记录 最小字母 的位置
        for i, curChar in enumerate(s):
            if curChar < s[pos]:
                pos = i

            if lastOccurrence[ord(curChar) - 97] == i:  # 当前curChar这个字母是最后一次出现在s中,就不能再向后找，需要退出循环
                break
        # 切片去掉 pos 以前的子串(包括pos，因为pos 以前的子串的所有字母在后面都还会出现)
        # 并删除后面所有的s[pos]
        subStr = s[pos + 1:].replace(s[pos], '')
        return s[pos] + self.removeDuplicateLetters1(subStr)

    def removeDuplicateLetters(self, s: str) -> str:
        return self.removeDuplicateLetters1(s)


if __name__ == "__main__":
    s = "cbacdcbc"
    print(Solution().removeDuplicateLetters(s))
